home *** CD-ROM | disk | FTP | other *** search
/ Acorn User: China / Acorn User China CD-ROM (UK) (Disc B) / Acorn User China CD-ROM (UK) (Disc B).bin / STUTTGART / TEMP / GNU / bison / Algorithm < prev    next >
Encoding:
Text File  |  1995-06-28  |  2.5 KB  |  68 lines
  1. Algorithm
  2. Previous: <Interface=>Interface> * Next: <Error Recovery=>ErrorRecov> * Up: <Top=>!Root>
  3.  
  4. #Wrap on
  5. {fH2}The Bison Parser Algorithm{f}
  6.  
  7. As Bison reads tokens, it pushes them onto a stack along with their
  8. semantic values.  The stack is called the {fUnderline}parser stack{f}.  Pushing a
  9. token is traditionally called {fUnderline}shifting{f}.
  10.  
  11. For example, suppose the infix calculator has read {fEmphasis}1 + 5 \*{f}, with a
  12. {fEmphasis}3{f} to come.  The stack will have four elements, one for each token
  13. that was shifted.
  14.  
  15. But the stack does not always have an element for each token read.  When
  16. the last {fStrong}n{f} tokens and groupings shifted match the components of a
  17. grammar rule, they can be combined according to that rule.  This is called
  18. {fUnderline}reduction{f}.  Those tokens and groupings are replaced on the stack by a
  19. single grouping whose symbol is the result (left hand side) of that rule.
  20. Running the rule's action is part of the process of reduction, because this
  21. is what computes the semantic value of the resulting grouping.
  22.  
  23. For example, if the infix calculator's parser stack contains this:
  24.  
  25. #Wrap off
  26. #fCode
  27. 1 + 5 \* 3
  28. #f
  29. #Wrap on
  30.  
  31. and the next input token is a newline character, then the last three
  32. elements can be reduced to 15 via the rule:
  33.  
  34. #Wrap off
  35. #fCode
  36. expr: expr '\*' expr;
  37. #f
  38. #Wrap on
  39.  
  40. Then the stack contains just these three elements:
  41.  
  42. #Wrap off
  43. #fCode
  44. 1 + 15
  45. #f
  46. #Wrap on
  47.  
  48. At this point, another reduction can be made, resulting in the single value
  49. 16.  Then the newline token can be shifted.
  50.  
  51. The parser tries, by shifts and reductions, to reduce the entire input down
  52. to a single grouping whose symbol is the grammar's start-symbol
  53. (\*Note <Language and Grammar=>Languagean>: Languages and Context-Free Grammars).
  54.  
  55. This kind of parser is known in the literature as a bottom-up parser.
  56.  
  57. #Wrap off
  58. <Look-Ahead=>LookAhead>:        Parser looks one token ahead when deciding what to do.
  59. <Shift/Reduce=>ShiftReduc>:      Conflicts: when either shifting or reduction is valid.
  60. <Precedence=>Precedencf>:        Operator precedence works by resolving conflicts.
  61. <Contextual Precedence=>Contextual>:  When an operator's precedence depends on context.
  62. <Parser States=>ParserStat>:     The parser is a finite-state-machine with stack.
  63. <Reduce/Reduce=>ReduceRedu>:     When two rules are applicable in the same situation.
  64. <Mystery Conflicts=>MysteryCon>:  Reduce\/reduce conflicts that look unjustified.
  65. <Stack Overflow=>StackOverf>:    What happens when stack gets full.  How to avoid it.
  66. #Wrap on
  67.  
  68.